package com.hspedu.sort;

import java.util.Arrays;

/**
 * @author Charlie
 * @version 1.0
 * @date 27/10/2025 下午10:02
 */
public class RadixSort {
    public static void main(String[] args) {
        int arr[] = {53, 3, 542, 748, 14, 214};
        radixSort3(arr);
    }

    public static void radixSort(int[] arr) {
        //根据推导结论，可以得到基数代码，先得到最大位数
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];

            }
        }

        //最大位数， 拼接字符串
        int maxLength = (max + "").length();


        int[][] bucket = new int[10][arr.length];
        //记录每个桶放的数据，再定义一个一维数组
        int[] bucketElementCounts = new int[10];


        //
        for (int i = 0, n = 1; i < maxLength; i++, n *= 10) {


            //第一轮 针对每个元素各位进行处理
            for (int j = 0; j < arr.length; j++) {
                int digitOfElement = arr[j] / n % 10;
                bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
                bucketElementCounts[digitOfElement]++;
            }

            //按照桶的顺序，把元素重新取出来
            int index = 0;
            // 遍历每一个桶
            for (int k = 0; k < bucket.length; k++) {
                if (bucketElementCounts[k] != 0) {
                    for (int l = 0; l < bucketElementCounts[k]; l++) {
                        arr[index++] = bucket[k][l];
                    }
                }
                bucketElementCounts[k] = 0;

            }

            System.out.println(Arrays.toString(arr));
        }

    }

    public static void radixSort2(int[] arr) {

        int Max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > Max) {
                Max = arr[i];
            }
        }
        int Maxlength = (Max + "").length();

        int[][] bucket = new int[10][arr.length];
        int[] buckCounter = new int[10];

        for (int i = 0, n = 1; i < Maxlength; i++, n *= 10) {


            for (int j = 0; j < arr.length; j++) {
                int digitElement = arr[j] / n % 10;
                bucket[digitElement][buckCounter[digitElement]] = arr[j];
                buckCounter[digitElement]++;
            }
            int index = 0;
            for (int k = 0; k < arr.length; k++) {
                if (buckCounter[k] != 0) {
                    for (int l = 0; l < buckCounter[k]; l++) {
                        arr[index++] = bucket[k][l];
                    }
                }
                buckCounter[k] = 0;
            }

        }

        System.out.println(Arrays.toString(arr));

    }

    public static void radixSort3(int arr[]) {
        int[][] bucket = new int[10][arr.length];
        int[] bucketCounter = new int[10];

        for (int j = 0; j < arr.length; j++) {
            int digitElement = arr[j] / 1 % 10;
            bucket[digitElement][bucketCounter[digitElement]] = arr[j];
            bucketCounter[digitElement]++;
        }
        int index = 0;
        for (int k = 0; k < bucket.length; k++) {
            if (bucketCounter[k] != 0) {
                for (int l = 0; l < bucketCounter[k]; l++) {
                    arr[index++] = bucket[k][l];
                }
                bucketCounter[k] = 0;
            }
        }

        System.out.println(Arrays.toString(arr));


    }


}
